package com.leetcode.题库;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2022-02-22 16:33
 */
public class 题库_1994_好子集的数目 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] nums = {10,11,5,1,10,1,3,1,26,11,6,1,1,15,1,7,22,1,1,1,1,1,23,1,29,5,6,1,1,29,1,1,21,19,1,1,1,2,1,11,1,15,1,22,14,1,1,1,1,6,7,1,14,3,5,1,22,1,1,1,17,1,29,2,1,15,10,1,5,7,1,1,1,30,1,30,1,21,10,1,1,1,1,1,2,6,5,7,3,1,1,19,29,1,7,13,14,1,5,26,19,11,1,1,1,1,1,1,1,1,22,15,1,1,13,1,17,1,1,1,13,6,1,10,1,1,17,1,1,3,14,7,17,1,13,1,1,1,1,1,11,1,1,6,1,1,1,1,1,2,1,30,2,26,1,1,14,1,26,29,30,1,13,21,1,1,14,21,1,23,1,15,23,21,1,30,19,19,1,10,23,3,3,17,22,2,26,1,11,1,23,1,1,1,15,1,1,13,1,1};
    long numberOfGoodSubsets = solution.numberOfGoodSubsets(nums);
    System.out.println(numberOfGoodSubsets);
  }

  static
  class Solution {

    Set<Integer> baseNums = new HashSet<>(Arrays.asList(
        1, 2, 3, 5, 6,
        7, 10, 11, 13, 14,
        15, 17, 19, 21, 22,
        23, 26, 29, 30));

    static final Map<Integer, List<Integer>> mutexNums = new HashMap<>();
    static {
      mutexNums.put(6, new ArrayList<>(Arrays.asList(2, 3)));
      mutexNums.put(10, new ArrayList<>(Arrays.asList(2, 5, 6)));
      mutexNums.put(14, new ArrayList<>(Arrays.asList(2, 7, 6, 10)));
      mutexNums.put(15, new ArrayList<>(Arrays.asList(3, 5, 6, 10)));
      mutexNums.put(21, new ArrayList<>(Arrays.asList(3, 7, 6, 14, 15)));
      mutexNums.put(22, new ArrayList<>(Arrays.asList(2, 11, 6, 10, 14)));
      mutexNums.put(26, new ArrayList<>(Arrays.asList(2, 13, 6, 10, 14, 22)));
      mutexNums.put(30, new ArrayList<>(Arrays.asList(2, 3, 5, 6, 10, 14, 15, 21, 22, 26)));
    }

    public int numberOfGoodSubsets(int[] nums) {
      long result = doNumberOfGoodSubsets(nums);
      return (int) (result % 1000000007);
    }

    public long doNumberOfGoodSubsets(int[] nums) {
      if (nums == null || nums.length == 0) {
        return 0;
      }

      if (nums.length == 1) {
        return nums[0] == 1 ? 0 : (baseNums.contains(nums[0]) ? 1 : 0);
      }

      Map<Integer, Integer> numCounts = new HashMap<>();
      for (int num : nums) {
        if (baseNums.contains(num)) {
          numCounts.compute(num, (key, oldValue) -> oldValue == null ? 1 : oldValue + 1);
        }
      }

      Set<Integer> curNumsSet = new HashSet<>(numCounts.keySet());
      boolean hasOne = curNumsSet.remove(1);
      if (curNumsSet.isEmpty()) {
        return 0;
      }
      int[] curNums = new int[curNumsSet.size()];
      int i = 0;
      for (int num : curNumsSet) {
        curNums[i++] = num;
      }
      Arrays.sort(curNums);

      Map<Integer, Boolean> mark = new HashMap<>();
      mark.put(1, false);
      mark.put(2, false);
      mark.put(3, false);
      mark.put(5, false);
      mark.put(6, false);
      mark.put(7, false);
      mark.put(10, false);
      mark.put(11, false);
      mark.put(13, false);
      mark.put(14, false);
      mark.put(15, false);
      mark.put(17, false);
      mark.put(19, false);
      mark.put(21, false);
      mark.put(22, false);
      mark.put(23, false);
      mark.put(26, false);
      mark.put(29, false);
      mark.put(30, false);

      int result = calculateCount(curNums, mark, 0, numCounts);
      if (hasOne) {
        Integer countOfOne = numCounts.get(1);
        long sum = 2;
        if (countOfOne % 2 == 1) {
          int temp = (countOfOne - 1) / 2;
          for (int k = 1; k <= temp; ++k) {
            long top = 1;
            long bottom = 1;
            for (int x = 1; x <= k; ++x) {
              top = top * (countOfOne - x + 1);
              bottom = bottom * x;
            }
            sum += (2 * (top / bottom));
          }
        } else {
          int temp = countOfOne / 2;
          for (int k = 1; k <= temp; ++k) {
            long top = 1;
            long bottom = 1;
            for (int x = 1; x <= k; ++x) {
              top = top * (countOfOne - x + 1);
              bottom = bottom * x;
            }
            sum += k == temp ? (top / bottom) : (2 * (top / bottom));
          }
        }
        return result * sum;
      }

      return result;
    }

    private int calculateCount(int[] nums, Map<Integer, Boolean> mark, int index, Map<Integer, Integer> numCounts) {
      if (index == nums.length) {
        int sum = 1;
        boolean flag = false;
        for (int num : nums) {
          if (mark.get(num)) {
            flag = true;
            sum *= numCounts.get(num);
          }
        }
        return flag ? sum : 0;
      }

      int result = 0;

      // 不要当前数
      result += calculateCount(nums, mark, index + 1, numCounts);

      // 不能要当前数
      if (mutexNums.containsKey(nums[index])) {
        List<Integer> mutexList = mutexNums.get(nums[index]);
        for (int mutexNum : mutexList) {
          if (mark.get(mutexNum)) {
            return result;
          }
        }
      }

      // 可以要当前数
      mark.put(nums[index], true);
      result += calculateCount(nums, mark, index + 1, numCounts);

      // 恢复
      mark.put(nums[index], false);

      return result;
    }
  }

}
